# 单纯的递归超过了时间限制
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not s:
            return True
        for i in range(len(s)):
            if s[:i+1] in wordDict:
                if self.wordBreak(s[i+1:], wordDict):
                    return True
        return False



class Solution:

    def wordBreak(self, s, wordDict):

        """

        :type s: str

        :type wordDict: List[str]

        :rtype: bool

        """

        if s == '':
            return True

        if len(wordDict) == 1:

            if s == wordDict[0]:

                return True

            else:

                return False

        dp = [0 for _ in range(len(s) + 1)]# dp是用来记录从哪个地方拆分可以将字符分成字典中的单词
        # 因为存在多个拆分方案，需要记录哪个位置拆分出的单词是dict中的
        dp[0] = 1

        for i in range(len(s)):

            str_ = s[:i + 1]

            for j in range(i + 1):

                if str_ in wordDict and dp[j]:
                    dp[i + 1] = 1

                str_ = str_[1:]
                print(dp)
        return dp[len(s)] == 1


test = Solution()
print(test.wordBreak("aaaaaaa", ["aaaa","aaa"]))